/*!
 * \file rdmaxclique.c
 *
 * \date Sep 24, 2013
 * \author Ricardo C. Corrêa (correa@lia.ufc.br)
 *
 * \brief Russian dolls algorithm for maximum clique.
 */

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <sys/time.h>

#include <bitmap.h>
#include <graph.h>
#include <grinput.h>
#include <heurPartiteSubgraph.h>
#include <mcr.h>

typedef struct {
	Node node;
	BitMap * R;
	BitMap * W;
} Doll;

static int (*maxPartiteSubgraph)(BitMap *, BitMap *, int);

static int (*sortVertices)(Graph *, int *);

void rd_maxClique(Graph * g, int maxdeg, long long * ndolls, long long * memsz) {
	int n = g->n;

	Doll stack[++maxdeg];
	Doll * doll = stack;
	*memsz = maxdeg * sizeof(Doll);

	BitMap * vec = newBitMapVector(maxdeg << 1, n);
//	*memsz += (maxdeg << 1) * nnodes * WSIZE;

	int i;
	for (i = 0; i < (maxdeg << 1); i++, doll++) {
		doll->R = vec + i++;
		doll->W = vec + i;
	}

	doll = stack;
	addAllElements(doll->R);
	int v = 0;

	initHeur(g);

	//initialize with a maximal clique
	if (g->maxcq < 0)
		g->maxcq = maxClique(doll->R);

	//build a coloring of the size of the maximal clique found
	mcsColoring_f(doll->R, doll->W, g->maxcq);

	int curC[n]; //!< Current clique
//	*memsz += n * sizeof(int);
	(*ndolls) = 1;

//	printSetNodes(doll->R);

	int topC = 0;
	int yesv = 0;
	beginWhile(doll->R, &doll->node);
	while (topC >= 0) {
//		printf("topC=%d\n",topC);
//		fflush(NULL);

		if (topC > g->maxcq) {
			yesv = curC[0];
//			//expand the current best clique
			int expc = expClique(doll->R, curC, topC);
//			maxStab(doll->R, doll->W, yesv);
			Node nodeR;
			setElement(&nodeR, yesv);
			addElement(doll->R, &nodeR);
			delElement(doll->W, &nodeR);
			mcsColoring_f(doll->R, doll->W, expc - g->maxcq);
			g->maxcq = expc;
			topC = 0;
		}

		Node nodev;
		//get the next vertex in the candidate set
		if (doll == stack)
		{
			nodev = doll->node;
			nextCommon(neig(g, yesv), &nodev);
			if (end(&nodev))
			{
				next(&doll->node);
				nodev = doll->node;
			}
		}
		else
		{
			next(&doll->node);
			nodev = doll->node;
		}

		if (end(&nodev)) {
			topC--;
			if (doll != stack)
				doll--;
		} else {
			v = getElement(&nodev);
//			printf("topC=%d  v=%d\n",topC,v);
//			fflush(NULL);
//			if ((*ndolls)>100)
//				exit(0);
			if (topC == g->maxcq) {
				doll = stack;
				curC[topC++] = v;
			} else {
				delElement(doll->R, &nodev);
				addElement(doll->W, &nodev);

				//Calculate the new candidate vector
				Doll * subdoll = doll + 1;
				//Check if the candidate vector is not empty
				//if (isReallyNotEmpty(doll->W)) { // && cardOfSet(subdoll->R, subdoll->minRNode, subdoll->maxRNode+1) >= max-topC-1) {

					intersectOf(subdoll->R, neig(g, v), doll->W);
					delAllElements(subdoll->W);

					//Build a coloring for the candidate's vector
					if (maxPartiteSubgraph(subdoll->R, subdoll->W, g->maxcq - topC - 1) == g->maxcq - topC - 1) {
						doll = subdoll;
						beginWhile(doll->R, &doll->node);
						curC[topC++] = v;
					}
					(*ndolls)++;
//				}
			}
		}
	}

	//	*memsz += getMemSize();

	freeBitMap(stack->R);
//	free(stack->R);

	closeHeur();
}

int main(int argc, char *argv[]) {
	char name[200];
	FILE* graphFile = NULL;
	FILE* outFile = NULL;

	outFile = fopen(argv[1], "a+");
	graphFile = fopen(argv[2], "r");
	strcpy(name, argv[2]);
	int algo;
	if (argc >= 4)
		algo = atoi(argv[3]);
	else
		algo = 1;

	switch (algo) {
	case 1: {
		maxPartiteSubgraph = greedyColoring;
		break;
	}
	case 2: {
		maxPartiteSubgraph = mcsColoring;
		break;
	}
	case 3: {
		printf("Not implemented.\n");
		exit(0);
		break;
	}
//	case 4: {
//		maxPartiteSubgraph = fracColoring;
//		break;
//	}
	}

	int order;
	if (argc >= 5)
		order = atoi(argv[4]);
	else
		order = 1;

	switch (order) {
	case 1: {
		sortVertices = heapMcr;
		break;
	}
	case 2: {
		sortVertices = listMcr;
		break;
	}
	case 3: {
		sortVertices = decExdegree;
		break;
	}
	case 4: {
		sortVertices = decDegree;
		break;
	}
	}

	Graph * g = readDimacsGraph(graphFile);

	struct timeval tvoi, tvoe;
	float renumberTime;

	int maxdeg;
	gettimeofday(&tvoi, NULL);
	int R[g->n];
	maxdeg = sortVertices(g, R);

	Graph * gg = newRenumbered(g, R);
	gettimeofday(&tvoe, NULL);

	printf("maxdeg=%d\n",maxdeg);
	fflush(NULL);

	renumberTime = (tvoe.tv_sec - tvoi.tv_sec) + (tvoe.tv_usec - tvoi.tv_usec) / 1000000000.0;
	delGraph(g);
	free(g);

	gg->maxcq = -1;
	if (argc >= 6)
	{
		char * fnm = strstr(argv[2], "random/");
		if (fnm != NULL)
		{
			fnm = strchr(fnm, '/')+1;
		}
		else
		{
			fnm = strrchr(argv[2], '/');
			if (fnm == NULL)
				fnm = argv[2];
			else
				fnm = fnm + 1;
		}
		fnm = strtok(fnm, ".");

		FILE * maxFile = fopen(argv[5], "r");
		char linestr[100];
		char * solfilename;
		while (!feof(maxFile) && gg->maxcq < 0)
		{
			if (fgets(linestr, 100, maxFile) == NULL)
				break;
			solfilename = strtok(linestr, " ");
			int maxcq = atoi(strtok(NULL, " "));
			printf("%s %s\n", fnm, solfilename);
			fflush(NULL);
			if (!strcmp(fnm, solfilename))
			{
				gg->maxcq = maxcq;
				printf("%s %d\n", solfilename, gg->maxcq);
				fflush(NULL);
			}
		}
		fclose(maxFile);
	}

	long long memsz;
	long long ndolls;

	struct timespec start, end;
	struct timeval tvs, tve;
	float optimizationTime;

	gettimeofday(&tvs, NULL);
	rd_maxClique(gg, maxdeg, &ndolls, &memsz);
	gettimeofday(&tve, NULL);
	start.tv_sec = tvs.tv_sec;
	start.tv_nsec = tvs.tv_usec * 1000;
	end.tv_sec = tve.tv_sec;
	end.tv_nsec = tve.tv_usec * 1000;
	optimizationTime = (end.tv_sec - start.tv_sec);
	optimizationTime += (end.tv_nsec - start.tv_nsec) / 1000000000.0;

	printf(
			"%s \t n=%d  colorHeur=%d  sortVert=%d  sol=%d  initTime=%f  ndolls=%lld  time=%f  mem=%fKB  graphmem=%fKB \n",
			name, gg->n, algo, order, gg->maxcq, renumberTime, ndolls,
			optimizationTime, memsz / 1024.0, gg->matrixsize / 1024.0);
	fprintf(outFile,
			"%s \t %d \t %d \t %d \t %d \t %f \t %lld \t %f \t %f \t %f\n",
			name, gg->n, algo, order, gg->maxcq, renumberTime, ndolls,
			optimizationTime, memsz / 1024.0, gg->matrixsize / 1024.0);

	delGraph(gg);
	free(gg);
	fclose(outFile);
	fclose(graphFile);
	return 0;
}
